class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    """业务逻辑是对的,但是时间会超"""
    def mergeKLists(self, lists: list) -> ListNode:
        head = ListNode(0)
        now_note = head
        for i in range(len(lists)):
            while now_note.next is not None:
                 now_note = now_note.next
            now_note.next = lists[i]
        while True:
            now_note, flag = head, True
            while now_note.next and now_note.next.next:
                if now_note.next.val > now_note.next.next.val:
                    now_note.next, now_note.next.next, now_note.next.next.next = \
                    now_note.next.next, now_note.next, now_note.next.next.next
                    flag = False
                now_note = now_note.next
            if flag:
                break
        return head.next


class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        mid_list, next_note = [], None
        for i in range(len(lists)):
            while lists[i]:
                mid_list.append(lists[i].val)
                lists[i] = lists[i].next
        mid_list.sort(reverse=True)
        if not mid_list:
            return None
        for num in mid_list:
            now_note = ListNode(num)
            now_note.next, next_note = next_note, now_note
        return next_note
